Sua Missão 🎯
Reconecte $N$ planetas, dados como coordenadas em 2D, com uma rede de "Hiper-Canal" de custo mínimo.
- Objetivo: Conecte todos os $N$ planetas (vértices) para que todos sejam alcançáveis (diretamente ou indiretamente).
- Objetivo: Encontre o projeto da rede que minimize o **custo total**.
Análise 🛰️
O custo de um canal (aresta) é a distância euclidiana:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- Um canal pode ser construído entre qualquerdois planetas.
- Isso significa que temos um grafo completo (denso).
A Solução ⚙️
Este é um problema clássico de Árvore Geradora Mínima (AGM) problema.
- Algoritmo: A pista recomenda Algoritmo de Prim (versão $O(V^2)$), que é perfeita para grafos densos.
- Ponto de Partida: Vamos iniciar nosso algoritmo a partir do Planeta 0 para garantir um resultado consistente.
Um grafo completo (esquerda) possui todas as arestas possíveis. A AGM (direita) é o subconjunto mais barato de arestas que conecta todos os vértices.